#define _CRT_SECURE_NO_WARNINGS 1


//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<stdbool.h>
//
//typedef struct QueueNode
//{
//	int val;
//	struct QueueNode* next;
//} QueueNode;
//
//typedef struct Queue
//{
//	QueueNode* phead;
//	QueueNode* ptail;
//	int size;
//} Queue;
//
//void QueueInit(Queue* pq)
//{
//	assert(pq);
//	pq->phead = pq->ptail = NULL;
//	pq->size = 0;
//}
//
//void QueuePush(Queue* pq, int x)
//{
//	assert(pq);
//	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
//	if (NewNode == NULL)
//	{
//		exit(1);
//	}
//	NewNode->val = x;
//	NewNode->next = NULL;
//	if (pq->phead == NULL)
//	{
//		pq->phead = pq->ptail = NewNode;
//	}
//	else
//	{
//		pq->ptail->next = NewNode;
//		pq->ptail = NewNode;
//	}
//	pq->size++;
//}
//
//bool QueueEmpty(Queue* pq)
//{
//	return pq->phead == NULL;
//}
//
//void QueuePop(Queue* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//	if (pq->phead == pq->ptail)
//	{
//		free(pq->phead);
//		pq->phead = pq->ptail = NULL;
//	}
//	else
//	{
//		QueueNode* next = pq->phead->next;
//		free(pq->phead);
//		pq->phead = next;
//	}
//	pq->size--;
//}
//
//int QueueFront(Queue* pq)
//{
//	return pq->phead->val;
//}
//
//int QueueBack(Queue* pq)
//{
//	return pq->ptail->val;
//}
//
//void QueueDestroy(Queue* pq)
//{
//	QueueNode* pcur = pq->phead;
//	while (pcur)
//	{
//		QueueNode* next = pq->phead->next;
//		free(pcur);
//		pcur = next;
//	}
//	pq->phead = pq->ptail = NULL;
//	pq->size = 0;
//}

//int main()
//{
//	Queue q;
//	QueueInit(&q);
//	QueuePush(&q, 1);
//	QueuePush(&q, 2);
//	QueuePush(&q, 3);
//	QueuePush(&q, 4);
//	QueuePop(&q);
//	QueuePop(&q);
//	printf("%d %d", QueueFront(&q), QueueBack(&q));
//
//	return 0;
//}


#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct Stack
{
	char* arr;
	int top;
	int capacity;
} Stack;

void StackInit(Stack* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, char x)
{
	if (ps->top == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		char* temp = (char*)realloc(ps->arr, sizeof(char) * NewCapacity);
		if (temp == NULL)
		{
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = NewCapacity;
	}
	ps->arr[ps->top++] = x;
}

bool StackEmpty(Stack* ps)
{
	return ps->top == 0;
}

void StackPop(Stack* ps)
{
	ps->top--;
}

char StackTop(Stack* ps)
{
	return ps->arr[ps->top - 1];
}

void StackDestroy(Stack* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

bool isValid(char* s)
{
	char* pi = s;
	Stack st;
	StackInit(&st);
	while (*pi != '\0')
	{
		if (*pi == '(' || *pi == '{' || *pi == '[')
		{
			StackPush(&st, *pi);
		}
		else
		{
			if (StackEmpty(&st))
			{
				StackDestroy(&st);
				return false;
			}
			char top = StackTop(&st);
			if ((top == '(' && *pi != ')')
				|| (top == '{' && *pi != '}')
				|| (top == '[' && *pi != ']'))
			{
				StackDestroy(&st);
				return false;
			}
			StackPop(&st);
		}
		pi++;
	}
	bool ret = StackEmpty(&st) ? true : false;
	StackDestroy(&st);
	return ret;
}

//int main()
//{
//	Stack st;
//	StackInit(&st);
//	StackPush(&st, 'A');
//	StackPush(&st, 'B');
//	StackPush(&st, 'C');
//	StackPush(&st, 'D');
//
//	return 0;
//}